#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <utility>

class Solution
{
public:
    std::vector<int> twoSum(std::vector<int> &nums, int target)
    {
        std::unordered_map<int, int> m;
        std::vector<int> res;
        for (int i = 0; i < nums.size(); ++i)
        {
            m[nums[i]] = i;
        }
        // 不能用 m.size(),m.size是key值的数量，且key值不可重复。
        for (int i = 0; i < nums.size(); ++i)
        {
            int t = target - nums[i];
            if (m.count(t) && m[t] != i)
            {
                res.push_back(i);
                res.push_back(m[t]);
                break;
                // return res;  // 这里return的话，如果没有匹配的结果，那么该函数就没有返回结果。
            }
        }
        return res;
    }
};

class Solution1
{
public:
    std::vector<int> twoSum(std::vector<int> &nums, int target)
    {
        std::vector<int> result;
        std::vector<std::pair<int, int>> data;
        for (int i = 0; i < nums.size(); ++i)
        {
            data.push_back(std::make_pair(nums[i], i));
        }
        std::sort(data.begin(), data.end());
        int min = 0;
        int max = nums.size() - 1;
        while (min < max)
        {
            if (data[min].first + data[max].first > target)
            {
                max--;
            }
            else if (data[min].first + data[max].first < target)
            {
                min++;
            }
            else
            {
                result.push_back(data[min].second);
                result.push_back(data[max].second);
                break;
            }
        }

        return result;
    }
};

int main(int argc, char **argv)
{
    std::vector<int> nums = {1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1};
    std::vector<int> result = Solution().twoSum(nums, 11);
    if (!result.empty())
    {
        std::cout << result[0] << " " << result[1] << std::endl;
    }
    std::vector<int> result1 = Solution1().twoSum(nums, 11);
    if (!result1.empty())
    {
        std::cout << result1[0] << " " << result1[1] << std::endl;
    }

    return 0;
}
